题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 $true$，否则返回 $false$。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

    5
   / \
  2   6
 / \
1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

1. $数组长度 <= 1000$

---

算法

(二叉搜索树,DFS) $O(n)$

根据后序序列和二叉搜索树的特性，在构造二叉搜索树（并不需要创建出真正的节点）的过程中判断是否出现矛盾，我们知道二叉搜索树的左子树的值要小于右子树，否则就不是一棵二叉搜索树。

如何构造二叉搜索树呢？

1. 根节点：后序序列的最后一个元素就是根节点
2. 而左子树中的值都是小于根节点的，所以从前往后遍历序列就可以找到第一个大于根节点的位置 $k$，从 $[l, k - 1]$ 就是左子树，$[k, r)$ 就是右子树

如何判断矛盾？

只要判断 $[k, r)$ 中的值是否都大于根节点即可

时间复杂度

$O(n)$

空间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    bool dfs(vector<int>& postorder, int l, int r) {
        if (l >= r) return true;
        int root = postorder[r];
        int k = l;
        while (k < r && postorder[k] < root) k ++ ;
        for (int i = k; i < r; i ++ )
            if (postorder[i] < root)
                return false;
        return dfs(postorder, l, k - 1) && dfs(postorder, k, r - 1);
    }

    bool verifyPostorder(vector<int>& postorder) {
        if (postorder.empty()) return true;
        return dfs(postorder, 0, postorder.size() - 1);
    }
};